

% 定义B树节点样式

\newpage


\section{树形DP的套路}

\begin{itemize}
	\item 确认左子树,返回什么信息,右子树返回什么信息, 
	\item `做资源整合求全集,就可以得到整棵树的信息`,不想对左数和右数的信息取进行定制化的开发,全部返回
	\item 左树,右树的信息,统统为整棵树的信息而服务
	
	\item 是否存在局部解, (左子树,右子树存在答案的可能性);
	\begin{itemize}
		\item 存在局部解,就需要,去细化左数对全集信息的影响
		\item 存在局部解,就需要去细化,右树对全集信息的影响
	\end{itemize}
	\item 开始封装 全集的信息体; 
	\item 存在局部解的情况,必须最后更新一次整体树的信息
	\begin{itemize}
		\item 在更新整数的信息值的时候,如果 待返回的全集信息 只剩一个, 直接使用三目运算符
		\item 在更新整数的信息值的时候,如果 待返回的全集信息 多于一个, 直接使用if分支进行判断
	\end{itemize}
	\item 不存在局部解,就直接 整合 左树,右树,以及整棵树的信息即可
\end{itemize}

\subsection{两个结点的最大距离}
\begin{equation*}\begin{split}
		Max_{(nodeDistance)} &= \\
		&Max(
		 \\&  Max(leftInfo.maxDistance, rightInfo.maxDistance),  \\&
		leftInfo.height + rightInfo.height + 1
		)
\end{split}\end{equation*}
 
  如果在整棵树上,那么最远的节点的距离应该是 
	
 
\begin{enumerate}
	\item 整棵树是一个满的二叉树
	
		\begin{tikzpicture}[level distance=1.5cm,
		level 1/.style={sibling distance=5cm},
		level 2/.style={sibling distance=3.0cm},
		level 3/.style={sibling distance=1.0cm},
		every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
		
		\node  {0}
		child {
			node   {5}
			child {
				node  {8}
				child {
					node  {14}
				}
				child {
					node  {11}
				}
			}
			child {
				node  {6}
				child {
					node  {12}
				}
				child {
					node  {7}
				}
			}
		}
		child {
			node   {1}
			child {
				node  {4}
				child {
					node  {13}
				}
				child {
					node  {9}
				}
			}
			child {
				node  {2}
				child {
					node  {10}
				}
				child {
					node  {3}
				}
			}
		};
		
	\end{tikzpicture}
	
	\item 答案在左子树
	
		\begin{tikzpicture}[level distance=1.5cm,
		level 1/.style={sibling distance=5cm},
		level 2/.style={sibling distance=3.0cm},
		level 3/.style={sibling distance=1.0cm},
		every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
		
		\node  {0}
		child {
			node   {5}
			child {
				node  {8}
				child {
					node  {14}
				}
				child {
					node  {11}
				}
			}
			child {
				node  {6}
				child {
					node  {12}
				}
				child {
					node  {7}
				}
			}
		}
		child {
			node   {1}
		};
		
	\end{tikzpicture}
	
	\item 答案在右子树
	
		\begin{tikzpicture}[level distance=1.5cm,
		level 1/.style={sibling distance=5cm},
		level 2/.style={sibling distance=3.0cm},
		level 3/.style={sibling distance=1.0cm},
		every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
		
		\node  {0}
		child {
			node   {5}
		}
		child {
			node   {1}
			child {
				node  {4}
				child {
					node  {13}
				}
				child {
					node  {9}
				}
			}
			child {
				node  {2}
				child {
					node  {10}
				}
				child {
					node  {3}
				}
			}
		};
		
	\end{tikzpicture}
\end{enumerate}


\subsection{返回满足最大搜索子树的头结点}

\subsection{一颗树是否是满二叉树}

\subsection{判断一颗树是完全二叉树}
\subsection{派对的最大快乐值问题}
\subsection{两个结点的最大距离}
\subsection{ 两个结点的最低公共祖先parent}

\section{集合操作}
\subsection{并查集-单集合操作O(1)}
他的内部有三个特别重要的结构数据,合并与查询两个元素是否属于同一集合的问题
\begin{enumerate}
	\item $Map<V,Node<V> >$流通货币的重要依据,在这里我们做的是自身,与自身的一个映射,就是一个泛型,没有任何的指针
	\begin{itemize}
		\item 这里可以有指针,也可以没有指针
		\item  这里不采用指针,使用parentNodeMap 来存储
	\end{itemize}
	\item $Map<Node<V>,Node<V> >$ 当前节点及其父节点的映射
	\item $Map<Node<V>,Integer>$ 已当前节点为头的节点个数,只保存头结点
\end{enumerate}
并查集（Disjoint Set Union，简称DSU）是一种数据结构，用于管理一组互不相交的集合，支持两种基本操作：
\begin{enumerate}
	\item Find（查找）：给定一个元素，确定它所在的集合。通常，我们希望找到集合的“根”节点，根节点是集合中没有父节点的节点，代表了整个集合。
	\item Union（合并）：将两个集合合并为一个集合。通常，这个操作会选取两个集合的根节点，并将其中一个根节点的父节点设置为另一个根节点，以确保最终只有一个根节点。
\end{enumerate}
并查集的主要目标是保持集合的“不相交性”，即在进行一系列合并操作后，任何两个属于不同集合的元素都不会有相同的根节点。并查集通常用于解决那些需要快速判断元素是否属于同一集合的问题，例如在图论中判断两个顶点是否连通。
并查集有两种常见的优化策略来提高效率：
\begin{itemize}
	\item 路径压缩（Path Compression）：在执行Find操作时，将每个节点的父节点直接指向根节点，减少查找深度。
	\item 按秩合并（Union by Rank）：在执行Union操作时，将较小集合的根节点指向较大集合的根节点，以保持树的平衡，减少树的高度。
\end{itemize}
这两种优化策略可以单独使用，也可以一起使用，以达到更好的性能。


\begin{enumerate}
	\item 	集合内的元素Array或者List,类型为V,这里就需要$Map<Node,Node<V>> nodesMap$ 来存储一下,本质就是做了一个最基本的数据和$Node<V>$映射后的一个表,一经初始化后,这个是Node作为流通货币的重要依据
	
	\begin{tikzpicture}[node distance=0.5cm and 0cm]
			\tikzstyle{nodestyle}=[draw, rectangle, minimum size=1.0cm, inner sep=0pt]
			\tikzstyle{nodeListstyle}=[draw, circle, minimum size=0.5cm, inner sep=0pt]
			\tikzstyle{linkStyle} = [left=0.1cm,align=center]
			\tikzstyle{linkTextStyle} = [below=0.5cm,align=center]
		
		\node [nodestyle] at (0,0)  {1};
		\node [nodestyle] at (1,0)  {2};
		\node [nodestyle] at (2,0)	{3};
		\node [nodestyle] at (3,0)	{4};
		\node [nodestyle] at (4,0)	{5};
		\node [nodestyle] at (5,0)	{6};
		\node [nodestyle] at (6,0)	{7};

	\end{tikzpicture}
	\item 集合内的元素,指向自身,这个使用$Map<Node, Node>  parentNodeMap$
	 
	来实现
	
	它表示一个映射，其中：
	\[
	\text{键（Key）}: \text{Node} \quad \text{值（Value）}: \text{Node}
	\]
	
	这意味着每一个节点（Node）对应另一个节点（Node），作为其父节点。
	
	\begin{tikzpicture}[level distance=1.5cm,
		level 1/.style={sibling distance=3cm},
		level 2/.style={sibling distance=2cm},
		level 3/.style={sibling distance=1.5cm},
		every node/.style={circle, draw}]
 
		\node (n0) at (0,0){1};
		\node (n1) at (1,0){2};
		\node (n2) at (2,0){3};
		\node (n3) at (3,0){4};
		\node (n4) at (4,0){5};
		\node (n5) at (5,0){6};
		\node (n6) at (6,0){7};
 
 		\path (n0) edge [loop above]  (n0)
				(n1) edge [loop above] (n1)
				(n2) edge [loop above] (n2)
				(n3) edge [loop above] (n3)
				(n4) edge [loop above] (n4)
				(n5) edge [loop above] (n5)
				(n6) edge [loop above] (n6); 			  
	\end{tikzpicture}
	
	parentNodeMap的数据如下:
	
	\begin{tabular}{|c|c|}
		\hline
		当前节点 & 父节点 \\
		1 & 1 \\
		2 & 2 \\
		3 & 3 \\
		4 & 4 \\
		5 & 5 \\
		6 & 6 \\
		\hline
	\end{tabular}
	
	sizeMap的数据如下
	
	\begin{tabular}{|c|c|}
		\hline
		头节点 & 已它为头节点的个数 \\
		1 & 1 \\
		2 & 1 \\
		3 & 1 \\
		4 & 1 \\
		5 & 1 \\
		6 & 1 \\
		\hline
	\end{tabular}
	\item 集合内的元素合并为一个集合
	
\begin{tikzpicture}[level distance=1.5cm,
	level 1/.style={sibling distance=3cm},
	level 2/.style={sibling distance=2cm},
	level 3/.style={sibling distance=1.5cm},
	every node/.style={circle, draw}]
	
	\node (n0) at (0,0) {1};
	\node (n1) at (1,0) {2};
	\node (n2) at (2,0) {3};
	\node (n3) at (3,0) {4};
	\node (n4) at (4,0) {5};
	\node (n5) at (5,0) {6};
	\node (n6) at (6,0) {7};
	
	\path (n0) edge [loop above] (n0)
	(n1) edge [right] (n0)
	(n2) edge [right] (n1)
	(n3) edge [right] (n2)
	
	(n4) edge [right] (n3)
	(n5) edge [right] (n4)
	(n6) edge [right] (n5);
	 
 % 添加箭头指向前一个节点
	\foreach [evaluate=\i as \prev using int(\i-1)] \i in {1,...,6} {
		\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n\prev);
	}
\end{tikzpicture}

	\begin{tabular}{|c|c|}
		\hline
		当前节点 & 父节点 \\
		1 & 1 \\
		2 & 1 \\
		3 & 2 \\
		4 & 3 \\
		5 & 4 \\
		6 & 5 \\
		\hline
	\end{tabular}
	
	\item 查找过程内的扁平化的处理
	
	\begin{enumerate}
		\item 父节点,父节点一致,不合并,见图\ref{fig:bainpinghua}
		\begin{figure}[htbp]
			\centering
			\begin{tikzpicture}[level distance=1.5cm,
				level 1/.style={sibling distance=1.0cm},
				level 2/.style={sibling distance=2cm},
				every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
				
				\node (n0) {1}
				child {
					node (n1) {2}
				}
				child {
					node (n2) {3}
				}
				child {
					node (n3) {4}
				}
				child {
					node (n4) {5}
				}
				child {
					node (n5) {6}
				}
				child {
					node (n6) {7}
				};
				
				% 添加箭头指向父节点
				\foreach \i in {1,...,6} {
					\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n0);
				}
				\path (n0) edge [loop above]  (n0);
			\end{tikzpicture}
			\caption{扁平化后的并查集结构}
			\label{fig:bainpinghua}
		\end{figure}
		
		parentNodeMap的数据如下
		
		\begin{tabular}{|c|c|}
			\hline
			当前节点 & 父节点 \\
			1 & 1 \\
			2 & 1 \\
			3 & 1 \\
			4 & 1 \\
			5 & 1 \\
			6 & 1 \\
			\hline
		\end{tabular}
		
			sizeMap的数据如下
		
		\begin{tabular}{|c|c|}
			\hline
			头节点 & 已它为头节点的个数 \\
			1 & 7 \\
			\hline
		\end{tabular}
		
		\item 父节点不一致,小节点挂载大节点
		
			\begin{tikzpicture}[level distance=1.5cm,
			level 1/.style={sibling distance=1.0cm},
			level 2/.style={sibling distance=2cm},
			every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
			
			\node (n0) {1}
			child {
				node (n1) {2}
			}
			child {
				node (n2) {3}
			}
			child {
				node (n3) {4}
			};
			
	 
			\begin{scope}[xshift=5cm]
	 			\node (n4) {5}
				child {
					node (n5) {6}
				}
				child {
					node (n6) {7}
				};
			\end{scope}
			
			
			
			% 添加箭头指向父节点
			\foreach \i in {1,...,3} {
				\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n0);
			}
			
			% 添加箭头指向父节点
			\foreach \i in {5,...,6} {
				\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n4);
			}
			\path (n0) edge [loop above]  (n0);
			\path (n4) edge [loop above]  (n4);
			
			
		\end{tikzpicture}
		
		由下图可见,1的子节点数为3;5的子节点数为2那么此时的大节点就是1,小节点就是5;所以节点5挂载到节点1
		
			\begin{tikzpicture}[level distance=1.5cm,
			level 1/.style={sibling distance=1.0cm},
			level 2/.style={sibling distance=2cm},
			every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
			
			\node (n0) {1}
			child {
				node (n1) {2}
			}
			child {
				node (n2) {3}
			}
			child {
				node (n3) {4}
			};
			
			
			\begin{scope}[xshift=5cm]
				\node (n4) {5}
				child {
					node (n5) {6}
				}
				child {
					node (n6) {7}
				};
			\end{scope}
			
			
			
			% 添加箭头指向父节点
			\foreach \i in {1,...,3} {
				\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n0);
			}
			
			% 添加箭头指向父节点
			\foreach \i in {5,...,6} {
				\draw[-stealth, shorten <=2pt, shorten >=2pt] (n\i) -- (n4);
			}
			\path (n0) edge [loop above]  (n0);
			\draw[-stealth, shorten <=2pt, shorten >=2pt] (n4)-- (n0);
			
			
		\end{tikzpicture}
		
		随即在find的过程中进行扁平化的处理,产生结果见图\ref{fig:bainpinghua}
	\end{enumerate}
			  
 
\end{enumerate}


\section{二叉树}
二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。这种结构上的限定使得二叉树成为计算机科学中研究和应用广泛的数据结构之一


%\begin{figure}
	%\centering
	\begin{tikzpicture}[
		%binary tree layout,node distance=1.3cm,nodes={circle,draw}
		]
		\node {1}
		child { node {2}
			child { node {3} }
			child { node {4}
				child { node {5} }
				child { node {6} }
			}
		}
		child { node {7}
			child[missing]
			child { node {8}
				child[missing]
				child { node {9} }
			}
		};
		
		\begin{scope}[xshift=5cm]
			\node {1}
			child { node {2}
				child { node {3} }
				child { node {4}
					child { node {5} }
					child { node {6} }
				}
			}
			child { node {7}
				child { node {4} }
				child { node {8}
					child[missing]
					child { node {9} }
				}
			};
		\end{scope}
	\end{tikzpicture}

	%\caption{二叉树示意图}
	\label{fig:exampleBTree}
%\end{figure}

 二叉树应该如上图所示\ref{fig:exampleBTree},左图为合法二叉树,右图为非法二叉树,树中不可交叉,不可有环
\subsection{前缀搜索树-词缀搜索树-Trie}

前缀搜索树（Trie，又称“字典树”或“前缀树”）是一种用于存储字符串的树形数据结构，它允许快速查找以特定前缀开头的字符串。在 Trie 树中，每个节点代表一个字符串，从根节点到某个节点的路径上的边上的字符序列构成了这个节点代表的字符串。下面是一个简单的前缀搜索树的概念性描述：
\begin{enumerate}
	\item 根节点：Trie 树的起始点，不包含任何字符。
	\item 节点：每个节点包含一个字符，以及指向其所有子节点的指针。如果一个节点没有子节\item 点，那么它代表一个完整的字符串。
	\item 边：从一个节点到另一个节点的边代表一个字符。从根节点到节点的路径上的边上的字符组合形成了节点代表的字符串。
	\item 子节点：每个节点可以有多个子节点，每个子节点对应树中的一个字符。
	\item 插入字符串：插入字符串时，遍历字符串中的每个字符，创建一条从当前节点到新节点的边，如果边已存在，则沿边向下；如果不存在，就创建一个新的节点并添加边。
	\item 查找字符串：从根节点开始，沿着与给定字符串匹配的字符路径向下遍历，如果到达叶子节点并且路径上的字符与给定字符串完全匹配，则字符串存在于 Trie 中。
\end{enumerate}

下图中的p为pass通过此字符的次数,e为end以此字符结尾的个数,以下字符的插入顺序
\begin{enumerate}
	\item a,aa,aad,aae,ab,ac,
	\item b,bd,be
	\item c,cb,cc
	\item d,da,db,dc
\end{enumerate}

\begin{tikzpicture}[level distance=1.5cm,
	level 1/.style={sibling distance=3.5cm},
	level 2/.style={sibling distance=1.0cm},
	Enode/.style={circle, draw, minimum size=0.5cm, inner sep=0pt},
	nodeDescription/.style={above left},
	arrow style/.style={->, shorten <=2pt, shorten >=2pt}]
	
	\node  (start) at (0,2) {start};
	\node[Enode] (n0) at (0,0) {}
	child {
		node[Enode] (n1) {a}
		child {
			node[Enode] (n11) {a}
			child {
				node[Enode] (n124) {d}
			}
			child {
				node[Enode] (n125) {e}
			}
		}
		child {
			node[Enode] (n12) {b}
		}
		child {
			node[Enode] (n13) {c}
		}
	}
	child {
		node[Enode] (n2) {b}
		child {
			node[Enode] (n24) {d}
		}
		child {
			node[Enode] (n25) {e}
		}
	}
	child {
		node[Enode] (n3) {c}
		child {
			node[Enode] (n32) {b}
		}
		child {
			node[Enode] (n33) {c}
		}
	}
	child {
		node[Enode] (n4) {d}
		child {
			node[Enode] (n41) {a}
		}
		child {
			node[Enode] (n42) {b}
		}
		child {
			node[Enode] (n43) {c}
		}
	};
	
	% 添加箭头指向父节点
	% 节点a
 	\path[->] (start)  edge node[align=left]{p=16\\e=0} (n0);
	\path[->] (n0) edge node[left, align=left] {p=6\\e=1} (n1);
	
		\path[->] (n1) edge node[above left, align=left] {p=3\\e=1} (n11);
			\path[->] (n11) edge node[above left, align=left] {p=1\\e=1} (n124);
			\path[->] (n11) edge node[right, align=right] {p=1\\e=1} (n125);
		
		\path[->] (n1) edge node[align=left] {p=3\\e=1} (n12);
		\path[->] (n1) edge node[above right,align=right] {p=3\\e=1} (n13);
		
	% 节点b
	\path[->] (n0) edge node[align=left] {p=3\\e=1} (n2);
		
		\path[->] (n2) edge node[left,align=left] {p=1\\e=1} (n24);
		\path[->] (n2) edge node[align=right] {p=1\\e=1} (n25);
	
	\path[->] (n0) edge node[align=left] {p=3\\e=1} (n3);
	
		\path[->] (n3) edge node[left,align=left] {p=1\\e=1} (n32);
		\path[->] (n3) edge node[align=right] {p=1\\e=1} (n33);
		
	\path[->] (n0) edge node[align=left] {p=4\\e=1} (n4);

		\path[->] (n4) edge node[left,align=left] {p=1\\e=1} (n41);
		\path[->] (n4) edge node[align=right] {p=1\\e=1} (n42);
		\path[->] (n4) edge node[right,align=right] {p=1\\e=1} (n43);
	% \path (n0) edge [loop above, arrow style]  (n0);
\end{tikzpicture}

\includegraphics[width=1.0\textwidth]{02-treeOperation/Multi-fork-tree/trie/String-trie.png}
\subsection{堆}

当需要快速访问最大/最小元素或进行优先级操作时，堆可能更快。

堆是一种特殊的树形数据结构，但它通常是指二叉堆。在二叉堆中，每个节点最多有两个子节点，这些子节点可以是左子节点和右子节点。二叉堆分为两种类型：最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，每个节点的值都大于或等于其子节点的值，而在最小堆中，每个节点的值都小于或等于其子节点的值。


\textbf{堆的两个特殊的操作,heapInsert/heapify}
\begin{itemize}
	\item   heapInsert: 上浮,堆位置调整
	\item    heapify: 下沉,堆位置调整
\end{itemize}

\textbf{堆化的优化,heapInsert/heapify}
\begin{itemize} 
	\item 已知元素个数的情况下，使用heapify（构建堆）的时间复杂度是$O(n)$。在数组中一次性构建堆时，可以从最后一个非叶子节点开始向上遍历，调整每个节点以满足堆的性质，因此时间复杂度是线性的。 
	\item 未知元素个数的情况下，每次插入新元素使用HeapInsert的时间复杂度是$O(log_2n)$。这是因为每次插入都需要从根节点向下遍历到适当位置，维护堆的性质，这个过程通常涉及的比较和交换次数对数级增长。 
\end{itemize}
\subsubsection{小顶堆}

	原数组
	
	\begin{tikzpicture}[node distance=0.5cm and 0cm]
		\tikzstyle{nodestyle}=[draw, rectangle, minimum size=1.0cm, inner sep=0pt]
		\tikzstyle{nodeListstyle}=[draw, circle, minimum size=0.5cm, inner sep=0pt]
		\tikzstyle{linkStyle} = [left=0.1cm,align=center]
		\tikzstyle{linkTextStyle} = [below=0.5cm,align=center]
		
		\node [nodestyle] at (0,0) {0};
		\node [nodestyle] at (1,0) {1};
		\node [nodestyle] at (2,0) {2};
		\node [nodestyle] at (3,0) {3};
		\node [nodestyle] at (4,0) {4};
		\node [nodestyle] at (5,0) {5};
		\node [nodestyle] at (6,0) {6};
		\node [nodestyle] at (7,0) {7};
		\node [nodestyle] at (8,0) {8};
		\node [nodestyle] at (9,0) {9};
		\node [nodestyle] at (10,0) {10};
		\node [nodestyle] at (11,0) {11};
		\node [nodestyle] at (12,0) {12};
		\node [nodestyle] at (13,0) {13};
		\node [nodestyle] at (14,0) {14};

	\end{tikzpicture}
 
 	堆化后的结果为
 	
	\begin{tikzpicture}[level distance=1.5cm,
		level 1/.style={sibling distance=5cm},
		level 2/.style={sibling distance=3.0cm},
		level 3/.style={sibling distance=1.0cm},
		every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
		
		\node  {0}
		child {
			node   {5}
			child {
				node  {8}
				child {
					node  {14}
				}
				child {
					node  {11}
				}
			}
			child {
				node  {6}
				child {
					node  {12}
				}
				child {
					node  {7}
				}
			}
		}
		child {
			node   {1}
			child {
				node  {4}
				child {
					node  {13}
				}
				child {
					node  {9}
				}
			}
			child {
				node  {2}
				child {
					node  {10}
				}
				child {
					node  {3}
				}
			}
		};
		
	\end{tikzpicture}
 
 \subsubsection{大顶堆}
 	原数组
 
 \begin{tikzpicture}[node distance=0.5cm and 0cm]
 	\tikzstyle{nodestyle}=[draw, rectangle, minimum size=1.0cm, inner sep=0pt]
 	\tikzstyle{nodeListstyle}=[draw, circle, minimum size=0.5cm, inner sep=0pt]
 	\tikzstyle{linkStyle} = [left=0.1cm,align=center]
 	\tikzstyle{linkTextStyle} = [below=0.5cm,align=center]
 	
 	\node [nodestyle] at (0,0) {0};
 	\node [nodestyle] at (1,0) {1};
 	\node [nodestyle] at (2,0) {2};
 	\node [nodestyle] at (3,0) {3};
 	\node [nodestyle] at (4,0) {4};
 	\node [nodestyle] at (5,0) {5};
 	\node [nodestyle] at (6,0) {6};
 	\node [nodestyle] at (7,0) {7};
 	\node [nodestyle] at (8,0) {8};
 	\node [nodestyle] at (9,0) {9};
 	\node [nodestyle] at (10,0) {10};
 	\node [nodestyle] at (11,0) {11};
 	\node [nodestyle] at (12,0) {12};
 	\node [nodestyle] at (13,0) {13};
 	\node [nodestyle] at (14,0) {14};
 	
 \end{tikzpicture}
 
 堆化后的结果为
 
	\begin{tikzpicture}[level distance=1.5cm,
	 	level 1/.style={sibling distance=5cm},
	 	level 2/.style={sibling distance=3.0cm},
	 	level 3/.style={sibling distance=1.0cm},
	 	every node/.style={circle, draw, minimum size=1cm, inner sep=0pt}]
	 	
	 	\node  {14}
	 	child {
	 		node   {9}
	 		child {
	 			node  {6}
	 			child {
	 				node  {0}
	 			}
	 			child {
	 				node  {3}
	 			}
	 		}
	 		child {
	 			node  {8}
	 			child {
	 				node  {2}
	 			}
	 			child {
	 				node  {7}
	 			}
	 		}
	 	}
	 	child {
	 		node   {13}
	 		child {
	 			node  {10}
	 			child {
	 				node  {1}
	 			}
	 			child {
	 				node  {5}
	 			}
	 		}
	 		child {
	 			node  {12}
	 			child {
	 				node  {4}
	 			}
	 			child {
	 				node  {11}
	 			}
	 		}
	 	};
	 	
 \end{tikzpicture}


\subsection{树结构的分类}

\subsubsection{相同树}

相同树指的是两个二叉树在结构上完全相同，并且每个对应节点的值也相等。也就是说，两棵树不仅形状一样，而且在相同位置的节点存储的值也相同。在算法实现上，通常会通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历两棵树，逐层比较节点的值和子树结构，以确定它们是否相同。

\begin{tikzpicture}[
	%binary tree layout,node distance=1.3cm,nodes={circle,draw}
	]
	% 跟节点
		\node {1}
		child { node {2}
			child { node {3} }
			child { node {4}
				child { node {5} }
				child { node {6} }
			}
		}
		child { node {7}
			child[missing]
			child { node {8}
				child[missing]
				child { node {9} }
			}
		};
		
		\begin{scope}[xshift=5cm]
					\node {1}
			child { node {2}
				child { node {3} }
				child { node {4}
					child { node {5} }
					child { node {6} }
				}
			}
			child { node {7}
				child[missing]
				child { node {8}
					child[missing]
					child { node {9} }
				}
			};
		\end{scope}
\end{tikzpicture}

	如上图所述,这就是相同树,两颗完全一致的树
	\begin{enumerate}
		\item 节点的内容一致
		\item 左子树完全一致
		\item 右子树完全一致

	\end{enumerate}
\subsubsection{镜面树}
镜面树（Mirror Tree 或 Symmetric Tree）： 镜面树通常指的是在一棵二叉树中，如果存在这样一种变换，即对树进行水平翻转（也就是交换所有节点的左右子树）之后，得到的树与原树结构相同，但方向相反，这样的树被称为镜像对称树或对称树。镜面树关注的是树的形状特性，而不是节点的具体值。在二叉树中，一个典型的例子是满二叉树或完全二叉树，当它们的所有非叶节点都没有值或者值相同，且左右子树互为镜像时，它们可以被视为自己的镜像树。


\begin{tikzpicture}[
	level/.style={sibling distance=40mm/#1},
	level distance=1.5cm,
	%nodes={circle, draw, minimum size=1cm}
	]
	% 跟节点
		\node {1}
		child { node {2}
			child { node {3} }
			child { node {4}
				child { node {5} }
				child { node {6} }
			}
		}
		child { node {2}
			child { node {4}
				child { node {6} }
				child { node {5} }
			}
			child { node {3} }
		};
\end{tikzpicture}
% BTree
\section{B-Tree}

B树（B-tree，有时也写作B-Tree或Btree）是一种自平衡的树形数据结构，特别适用于外部存储或磁盘存储系统，因为它能够减少磁盘I/O操作次数，从而提高效率。B树的设计初衷是为了满足文件系统和数据库系统中大量数据存储和快速查找的需求。以下是B树的一些关键特性：
\begin{enumerate}
	\item 多路平衡查找树：与二叉树不同，B树的每个节点可以有多个子节点，通常子节点的数量在一个预先设定的最小值(t)到%最大值(2t-1)之间（(t \geq 2)），
	这意味着B树是一种多路平衡查找树。
	\item 自平衡：每当有新数据插入或删除时，B树都会通过分裂、合并节点或重新分配节点中的键值来自动维护树的平衡状态，确保树的高度保持在对数级别，从而保证查找、插入和删除操作的高效性。
	\item 有序结构：B树中的所有节点都按照键值的大小顺序排列，每个节点包含一个或多个键值及其关联的数据或指向下一层节点的指针。
	\item 分支因子：B树的分支因子（每个节点的子节点数）相对较大，这有助于减少树的高度，特别是在磁盘I/O密集型操作中尤为重要，因为每次I/O操作涉及的节点数更多。
	\item 搜索效率：由于B树的高度较低，对于包含大量数据的树，搜索、插入和删除操作的时间复杂度可以保持在对数级别，通%常是(O(log_{t}N))，其中(N)是树中节点的数量，(t)是分支因子。
	应用场景：B树广泛应用于数据库索引、文件系统（如Ext4、NTFS）以及其他需要高效随机访问大量数据的场景。
\end{enumerate}

在这里我们以5叉为例,那么此时的m=5，那么他的分支数为$ \lceil \frac{m}{2} \rceil - 1 \leq n \leq m - 1$ ,

其中n为分支树,我们以插入的节点顺序为 
C,N,G,A,H,E,K,Q,M,F,W,L,T,Z,D,P,R,X,Y,S

\begin{enumerate}
	\item \textbf{插入 C,N,G,A节点时,进行排序比较}
	
	\begin{tikzpicture}[grow=down, sloped,treenode/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.5cm,
			font=\small},
		every node/.style = {treenode},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node [treenode] {A \nodepart{two} C \nodepart{three} G \nodepart{four} N};
		
	\end{tikzpicture}
	
	\item \textbf{此时n=4,当插入下一个节点H时,n=5 $>$ 4,中间节点G化为根节点,两边分裂}
	
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
			,treenode_3/.style = {
				rectangle split,
				rectangle split parts=3,
				draw,
				align=center,
				rectangle split horizontal,
				text width=0.5cm,
				font=\small},
						,treenode_2/.style = {
					rectangle split,
					rectangle split parts=2,
					draw,
					align=center,
					rectangle split horizontal,
					text width=0.5cm,
					font=\small},
							,treenode_1/.style = {
						rectangle split,
						rectangle split parts=1,
						draw,
						align=center,
						rectangle split horizontal,
						text width=1.0cm,
						font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node  { G }
		child{node[treenode_2]{A \nodepart{two} C	}}
		child{node[treenode_2]{H \nodepart{two} N	}};
		
	\end{tikzpicture}
	
	\item 当插入E节点时,与根节点H 比较,$<G$ ,去G的左子树
	
		\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node  { G }
		child{node[treenode_3]{A \nodepart{two} C \nodepart{three} E}}
		child{node[treenode_2]{H \nodepart{two} N	}};
		
	\end{tikzpicture}
	
	\item \textbf{插入节点K时,与根节点G比较,去G的右子树}
	
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node  { G }
		child{node[treenode_3]{A \nodepart{two} C \nodepart{three} E}}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} N }};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点Q,与根节点G相比,去G的右子树}
		
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node  { G }
		child{node[treenode_3]{A \nodepart{two} C \nodepart{three} E}}
		child{node[treenode_4]{H \nodepart{two} K \nodepart{three} N \nodepart{four} Q}};
		
	\end{tikzpicture}
	\item \textbf{当插入节点M,与根节点G相比,去G的右子树,此时右子树为4个节点,已经满了,需要中间节点M升级为根节点并入到根节点G中,两边节点分裂}


			\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_2]  { G \nodepart{two} M}
		child{node[treenode_3]{A \nodepart{two} C \nodepart{three} E}}
		child{node[treenode_2]{H \nodepart{two} K }}
		child{node[treenode_2]{N \nodepart{two} Q }};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点F,与根节点相比,在G的左子树中}
	
			\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_2]  { G \nodepart{two} M}
		child{node[treenode_4]{A \nodepart{two} C \nodepart{three} E \nodepart{four} F }}
		child{node[treenode_2]{H \nodepart{two} K }}
		child{node[treenode_2]{N \nodepart{two} Q }};
		
	\end{tikzpicture}
	\item \textbf{当插入节点W,与根节点相比,在M的右子树}
	
				\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_2]  { G \nodepart{two} M}
		child{node[treenode_4]{A \nodepart{two} C \nodepart{three} E \nodepart{four} F }}
		child{node[treenode_2]{H \nodepart{two} K }}
		child{node[treenode_3]{N \nodepart{two} Q \nodepart{three} W}};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点L,与根节点相比$G<L<M$ ,在G,M的中间}
	
					\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_2]  { G \nodepart{two} M}
		child{node[treenode_4]{A \nodepart{two} C \nodepart{three} E \nodepart{four} F }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_3]{N \nodepart{two} Q \nodepart{three} W}};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点T 时,与根节点比较,$M<T$,在M的右子树}
			
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_2]  { G \nodepart{two} M}
		child{node[treenode_4]{A \nodepart{two} C \nodepart{three} E \nodepart{four} F }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_4]{N \nodepart{two} Q \nodepart{three} T \nodepart{four} W}};
		
	\end{tikzpicture}

	\item \textbf{当插入节点Z 时,与根节点比较$M<Z$,在M的右子树,此时M的右子树已经存在了4个节点,所以中间节点T升级为跟节点,合并至G,M中,两边节点分裂}
	

	
	
		\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_3]  { G \nodepart{two} M \nodepart{three} T}
		child{node[treenode_4]{A \nodepart{two} C \nodepart{three} E \nodepart{four} F }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_2]{N \nodepart{two} Q }}
		child{node[treenode_2]{W \nodepart{two} Z }};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点D 时,与根节点比较$D<G$,在G的左子树中,此时G的左子树已经存在了4个节点,所以需要中间节点D升级为根节点,合并值G,M,T中,两边节点分裂}
	
			\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_4]  {D \nodepart{two} G \nodepart{three} M \nodepart{four} T}
		child{node[treenode_2]{A \nodepart{two} C  }}
		child{node[treenode_2]{E \nodepart{two} F  }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_2]{N \nodepart{two} Q }}
		child{node[treenode_2]{W \nodepart{two} Z }};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点P 时,与过根节点相比$M<P<T$,在M和T之间,}
	
				\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_4]  {D \nodepart{two} G \nodepart{three} M \nodepart{four} T}
		child{node[treenode_2]{A \nodepart{two} C  }}
		child{node[treenode_2]{E \nodepart{two} F  }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_3]{N \nodepart{two} P \nodepart{three} Q}}
		child{node[treenode_2]{W \nodepart{two} Z }};
		
	\end{tikzpicture}
	
	\item \textbf{当插入节点R 时,与根节点相比$M<R<T$,在M,T之间}
	
		\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_4]  {D \nodepart{two} G \nodepart{three} M \nodepart{four} T}
		child{node[treenode_2]{A \nodepart{two} C  }}
		child{node[treenode_2]{E \nodepart{two} F  }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_4]{N \nodepart{two} P \nodepart{three} Q \nodepart{four} R}}
		child{node[treenode_2]{W \nodepart{two} Z }};
		
	\end{tikzpicture}
	\item \textbf{当插入节点X 时,和根节点比较$T<X$,在T的右子树}
	
			\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_4]  {D \nodepart{two} G \nodepart{three} M \nodepart{four} T}
		child{node[treenode_2]{A \nodepart{two} C  }}
		child{node[treenode_2]{E \nodepart{two} F  }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_4]{N \nodepart{two} P \nodepart{three} Q \nodepart{four} R}}
		child{node[treenode_3]{W \nodepart{two} X \nodepart{three} Z}};
		
	\end{tikzpicture}
	\item \textbf{当插入节点Y 时和根节点比较$T<Y$,在T的右子树}
	
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.5cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=1.0cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=3cm, level distance=2cm},
		level 2/.style = {sibling distance=2.5cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		\node[treenode_4]  {D \nodepart{two} G \nodepart{three} M \nodepart{four} T}
		child{node[treenode_2]{A \nodepart{two} C  }}
		child{node[treenode_2]{E \nodepart{two} F  }}
		child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		child{node[treenode_4]{N \nodepart{two} P \nodepart{three} Q \nodepart{four} R}}
		child{node[treenode_4]{W \nodepart{two} X \nodepart{three} Y \nodepart{four} Z}};
		
	\end{tikzpicture}
	\item \textbf{当插入节点S 时,和根节点比较$M<S<T$,在M,T之间,由于已经存在了4个节点,所以需要中间节点Q升级为根节点,合并至D,G,M,T中,由于根节点已经存在了4个节点中间结点M升级为跟节点,两边节点分裂;同时N,P,R,S分裂为两边节点}
	
		
	\begin{tikzpicture}[grow=down, sloped,treenode_4/.style = {
			rectangle split,
			rectangle split parts=4,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.2cm,
			font=\small},
		,treenode_3/.style = {
			rectangle split,
			rectangle split parts=3,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.2cm,
			font=\small},
		,treenode_2/.style = {
			rectangle split,
			rectangle split parts=2,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.2cm,
			font=\small},
		,treenode_1/.style = {
			rectangle split,
			rectangle split parts=1,
			draw,
			align=center,
			rectangle split horizontal,
			text width=0.2cm,
			font=\small},
		every node/.style = {treenode_1},
		level 1/.style = {sibling distance=5cm, level distance=2cm},
		level 2/.style = {sibling distance=1.5cm, level distance=1.5cm},
		level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
		
		\node {M}
		child{
			node[treenode_2]  {D \nodepart{two} G }
			child{node[treenode_2]{A \nodepart{two} C  }}
			child{node[treenode_2]{E \nodepart{two} F  }}
			child{node[treenode_3]{H \nodepart{two} K \nodepart{three} L}}
		}
		child{
			node[treenode_2]  {Q \nodepart{two} T }
			child{node[treenode_2]{N \nodepart{two} P }}
			child{node[treenode_2]{R \nodepart{two} S }}
			child{node[treenode_4]{W \nodepart{two} X \nodepart{three} Y \nodepart{four} Z}}
		};
 
	\end{tikzpicture}
\end{enumerate}
 